#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
	vector<int> gardenNoAdj(int n, vector<vector<int>>& paths)
	{
		vector<int> G[n];
		for (int i = 0, len = paths.size(); i < len; i++) {
			vector<int>& path = paths[i];
			G[path[0] - 1].emplace_back(path[1] - 1);
			G[path[1] - 1].emplace_back(path[0] - 1);
		}

		vector<int> ans(n, 0);
		for (int i = 0; i < n; i++) {
			int colorSet = 0xf;
			vector<int>& neighbor = G[i];
			for (int j = 0, len = neighbor.size(); j < len; j++) {
				int color = ans[neighbor[j]];
				if (color) colorSet &= -1 - (1 << (color - 1));
			}
			for (int j = 0; j < 4; j++)
				if (colorSet & (1 << j)) {
					ans[i] = j + 1;
					break;
				}
		}

		return ans;
	}
};

int main()
{
	return 0;
}
